package hot;

public class sanerer {
    class Solution {
        public int coinChange(int[] coins, int amount) {
            int n=coins.length;
            int[] f=new int[amount+1];
            for(int j=1;j<=amount;j++){
                f[j]=-1;
            }
            for(int i=1;i<n+1;i++){
                for(int j=0;j<=amount;j++){
                    if(j-coins[i-1]>=0&&f[j-coins[i-1]]!=-1){
                        //这里有可能f[i][j]==-1，这样子必取到-1
                        //故单独判断，若f[i][j]==-1 就直接取f[i][j-coins[i-1]]+1
                        if(f[j]==-1){
                            f[j]=f[j-coins[i-1]]+1;
                        }else{
                            //若f[i][j]！=-1 才取二者的较小值
                            f[j]=Math.min(f[j],f[j-coins[i-1]]+1);
                        }
                    }
                }
            }
            return f[amount];


        }
    }
}
